#include <iostream>
#include <queue>
#include <stdexcept>  // 添加这个头文件以使用runtime_error
using namespace std;

/**
 * 用两个队列实现栈
 * 栈特性：后进先出 (LIFO)
 * 队列特性：先进先出 (FIFO)
 * 
 * 实现思路：
 * 1. 使用两个队列：主队列(mainQueue)和辅助队列(helperQueue)
 * 2. 入栈操作：
 *    - 将新元素加入辅助队列
 *    - 将主队列的所有元素依次出队并加入辅助队列
 *    - 交换两个队列的角色（这样新元素就在主队列的头部）
 * 3. 出栈操作：直接从主队列出队
 */
class QueueStack {
private:
    queue<int> mainQueue;    // 主队列，存储栈元素
    queue<int> helperQueue;  // 辅助队列，用于入栈操作
    
public:
    QueueStack() {
        cout << "初始化双队列栈" << endl;
    }
    
    /**
     * 入栈操作 - 时间复杂度: O(n)
     * 通过两个队列的配合，使得新加入的元素总是在队列头部
     */
    void push(int x) {
        cout << "入栈元素: " << x << endl;
        
        // 1. 先将新元素加入辅助队列
        helperQueue.push(x);
        
        // 2. 将主队列的所有元素依次出队并加入辅助队列
        //    这样新元素就在辅助队列的头部，其他元素保持相对顺序
        while (!mainQueue.empty()) {
            helperQueue.push(mainQueue.front());  // 将主队列队首加入辅助队列
            mainQueue.pop();                      // 主队列出队
        }
        
        // 3. 交换两个队列的角色
        //    现在辅助队列包含了所有元素，且新元素在头部
        swap(mainQueue, helperQueue);
        
        printStatus();
    }
    
    /**
     * 出栈操作 - 时间复杂度: O(1)
     * 直接从主队列出队即可（因为入栈时已经保证了栈顶元素在队列头部）
     */
    int pop() {
        if (empty()) {
            throw runtime_error("栈为空，无法出栈");
        }
        
        int top = mainQueue.front();  // 获取栈顶元素
        mainQueue.pop();              // 弹出栈顶元素
        cout << "出栈元素: " << top << endl;
        printStatus();
        return top;
    }
    
    /**
     * 获取栈顶元素 - 时间复杂度: O(1)
     */
    int top() {
        if (empty()) {
            throw runtime_error("栈为空");
        }
        return mainQueue.front();
    }
    
    /**
     * 判断栈是否为空
     */
    bool empty() {
        return mainQueue.empty();
    }
    
    /**
     * 获取栈的大小
     */
    int size() {
        return mainQueue.size();
    }
    
    /**
     * 打印栈当前状态（用于调试）
     */
    void printStatus() {
        cout << "栈大小: " << size() 
             << ", 栈是否为空: " << (empty() ? "是" : "否");
        if (!empty()) {
            cout << ", 栈顶元素: " << top();
        }
        cout << endl;
    }
};

/**
 * 单队列实现栈的替代方案
 * 实现思路：在入栈时通过循环移动元素来维护栈的顺序
 */
class SingleQueueStack {
private:
    queue<int> q;  // 单个队列
    
public:
    SingleQueueStack() {
        cout << "初始化单队列栈" << endl;
    }
    
    /**
     * 入栈操作 - 时间复杂度: O(n)
     * 1. 将新元素加入队列
     * 2. 将队列中除新元素外的所有元素依次出队再入队
     *    这样新元素就在队列头部
     */
    void push(int x) {
        cout << "入栈元素: " << x << " (单队列实现)" << endl;
        int n = q.size();  // 记录当前队列大小
        q.push(x);         // 加入新元素
        
        // 将前面的n个元素依次移到新元素后面
        for (int i = 0; i < n; i++) {
            q.push(q.front());  // 将队首元素加入队尾
            q.pop();            // 移除原队首元素
        }
    }
    
    int pop() {
        if (empty()) {
            throw runtime_error("栈为空");
        }
        int top = q.front();
        q.pop();
        cout << "出栈元素: " << top << " (单队列实现)" << endl;
        return top;
    }
    
    int top() {
        if (empty()) {
            throw runtime_error("栈为空");
        }
        return q.front();
    }
    
    bool empty() {
        return q.empty();
    }
    
    int size() {
        return q.size();
    }
};

/**
 * 测试用队列实现的栈
 */
int main() {
    cout << "=== 测试：用两个队列实现栈 ===" << endl;
    QueueStack stack;
    
    // 测试1：基本入栈出栈操作
    cout << "\n--- 测试1：基本操作 ---" << endl;
    stack.push(1);
    stack.push(2);
    stack.push(3);
    
    cout << "栈顶元素: " << stack.top() << endl;  // 应该输出3
    cout << "出栈: " << stack.pop() << endl;      // 应该输出3
    
    // 测试2：混合操作
    cout << "\n--- 测试2：混合操作 ---" << endl;
    stack.push(4);
    stack.push(5);
    
    cout << "栈顶元素: " << stack.top() << endl;  // 应该输出5
    cout << "出栈: " << stack.pop() << endl;      // 应该输出5
    cout << "出栈: " << stack.pop() << endl;      // 应该输出4
    
    // 测试3：连续出栈直到空
    cout << "\n--- 测试3：清空栈 ---" << endl;
    while (!stack.empty()) {
        cout << "出栈: " << stack.pop() << " ";
    }
    cout << endl;
    
    // 测试4：单队列实现栈
    cout << "\n--- 测试4：单队列实现栈 ---" << endl;
    SingleQueueStack singleStack;
    singleStack.push(10);
    singleStack.push(20);
    singleStack.push(30);
    
    cout << "栈顶元素: " << singleStack.top() << endl;  // 应该输出30
    cout << "出栈: " << singleStack.pop() << endl;      // 应该输出30
    cout << "栈顶元素: " << singleStack.top() << endl;  // 应该输出20
    
    cout << "\n=== 测试完成 ===" << endl;
    return 0;
}
